﻿namespace MyLeetCode.Tool
{
    public class MyTool
    {
        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="list">数据容器</param>
        /// <param name="target">查询目标</param>
        /// <param name="sorted">是否排序</param>
        /// <typeparam name="T">数据类型</typeparam>
        /// <returns></returns>
        public int BinarySearch<T>(
            List<T> list,
            T target,
            bool sorted=true)
            where T : IComparable<T>
        {
            if (!sorted)
            {
                list.Sort();
            }
            int lp = 0;
            int rp = list.Count - 1;
            int result = -1;
            while (lp <= rp)
            {
                int mp = (lp + rp) / 2;
                int comp = list[mp].CompareTo(target);
                if (comp == 0)
                {
                    result = mp;
                    break;
                }
                else
                if (comp < 0)
                {
                    lp = mp + 1;
                }
                else
                {
                    rp = mp - 1;
                }
            }
            return result;
        }

        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="list">数据容器</param>
        /// <param name="target">查询目标</param>
        /// <param name="lp">左指针</param>
        /// <param name="rp">右指针</param>
        /// <param name="sorted">是否排序</param>
        /// <typeparam name="T">数据类型</typeparam>
        /// <returns></returns>
        public int BinarySearch<T>(
            List<T> list,
            T target,
            int lp,
            int rp,
            bool sorted=true)
        where T : IComparable<T>
        {
            if (!sorted)
            {
                list.Sort();
            }
            int result = -1;
            while (lp <= rp)
            {
                int mp = (lp + rp) / 2;
                int comp = list[mp].CompareTo(target);
                if (comp == 0)
                {
                    result = mp;
                    break;
                }
                else
                if (comp < 0)
                {
                    lp = mp + 1;
                }
                else
                {
                    rp = mp - 1;
                }
            }
            return result;
        }
    }
}